The coding of video signals for efficient transmission and/or storage has received a great deal of recent attention, particularly with the growing interest in technologies such as HDTV (High Definition Television) and Interactive Television (e.g., "video-on-demand"). In fact, video coding algorithms have been standardized for many of these applications (e.g., Motion Picture Experts Group standards such as MPEG-1 and MPEG-2). These applications, however, typically involve the coding of video signals at coding rates above 56 kbits/s (kilobits per second).
The techniques used in these applications most commonly code each video frame (i.e., each individual still image) at a variable bit rate and then use buffering to obtain a fixed data rate for transmission or storage. Coded frames may be dropped (i.e., the previous frame is repeated on decoding) if the average rate over successive frames would cause the buffer to overflow. The result is that the decoded video has an effectively variable frame rate and a delay (in addition to the transmission delay) due to the buffer.
In video communications applications (e.g., video telephones) the available bandwith (i.e., maximum bit rate) may be substantially less than that which is available in other applications. If the coded video signal is intended for transmission across a conventional telephone line with the use of a conventional modem, bit rates may well be limited to 19.2 kbits/s or even to 9.6 kbits/s based on current modem technology. However, when the above-described techniques are used at bit rates much lower than 56 kbits/s the resultant decoded video is often unacceptable. For example, since the buffer delay is proportional to the inverse of the maximum coded frame rate, and since the coded frame rate is often reduced in order to achieve the lower coding bit rates, unacceptable delay may be introduced. In addition, the reduced coding rate requires more frequent frame repeats, and thus results in an unacceptably low average frame rate. To overcome these problems, it would be advantageous to encode each frame at a constant bit rate, thereby eliminating the need for buffering, avoiding the associated delay and maintaining a constant frame rate in the resultant decoded video. However, like their variable bit-rate counterparts, conventional fixed bit-rate video coding techniques have not been able to achieve acceptable quality levels at these low bit rates.
A common approach to video signal coding involves the use of vector quantization codebooks. The general principles of vector quantization and the use of vector quantization codebooks are described in detail in A. Gersho and R. M. Gray, Vector Quantization and Signal Compression, Kluwer Academic Publishers, Boston Mass., 1992. In such an approach, each frame is typically divided into frame portions referred to as "vectors" or "blocks." Each of these blocks contains the signal data for a plurality of pixels (individual picture elements). Depending, for example, on the available bit rate, some or all of these blocks are then quantized and compared with entries in a codebook to find the best match. The index of the best matching codebook entry is then transmitted to the decoder which contains an identical codebook. Thus, the codebook entry index is used to represent the given block. This form of coding, in which the pixels of a given frame are coded irrespective of the content of other frames, is known as "intraframe" coding.
Most often, the blocks to be coded are transformed into a frequency domain (e.g., with use of a Discrete Cosine Transformation) before quantization, and a corresponding inverse transformation is performed by the decoder. Thus, the codebook entries are frequency domain entries. In addition, the coder may use "interframe" coding techniques, in addition to the previously described intraframe coding technique, when it is advantageous to do so. In interframe coding, each block to be coded (or, more commonly, its transform) is compared with a corresponding block of pixels (or its transform) from a previous frame, and the difference between the two is quantized and matched against an "interframe" codebook containing difference entries. Moreover, the pixels from the previous frame may be "motion compensated" in order to produced a better match (i.e., a smaller difference from the block to be coded). That is, portions of the previous frame are relocated within the image and compared to the current frame to determine "motion vectors" which represent the movement in the scene.
Typically, when performing interframe coding, it is advantageous to incorporate the decoder circuitry within the encoder to "reconstruct" the previous frame data. In this manner, the difference analysis performed by the encoder will advantageously be based on the decoded previous frame (since the decoding of the current frame in the decoder will also be so based), resulting in a more accurate coding of the present frame.
One particular approach which has been taken in certain signal coding techniques involves the use of adaptive codebooks, which are described in Chapter 11 of Gersho and Gray. Adaptive codebooks change over time in an attempt to provide a better match to the local statistics of the signal being coded. That is, the codebook, and thereby the coder, adapts to the characteristics of the signal. In a video application, such an approach can result in an improved quality of the decoded video, since the coder is, in effect, adapting itself to the given scene (i.e., the particular objects and motion contained therein).
Forward adaptive codebook schemes use information from the frame to be coded to modify and, hopefully, thereby improve, the codebook. Such techniques typically replace one or more of the codebook entries with new entries before coding the current frame. Blocks which might otherwise not be coded well (i.e., with a sufficiently small error) might form the basis of a new codebook entry, thereby, e.g., resulting in an improved or even error-free coding of the given block. However, since the decoder must be supplied with the codebook update, additional information, known as "side" information, has to be separately coded and transmitted by these forward adaptive techniques, so that the current frame can be properly decoded by the decoder. Therefore, despite their ability to adapt the coder to the scene when used in video applications, the use of these forward adaptive schemes has heretofore been inconsistent with the use of fixed bit-rate coding.